/**
 * describe:
 *
 * @author chaP
 * @date 2019/01/22
 */
package CodingTest.AC20190122;

import java.util.HashMap;

/**
 * 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

 你可以假设数组是非空的，并且给定的数组总是存在众数。

 示例 1:

 输入: [3,2,3]
 输出: 3
 */
public class majorityElement {
    public static void main(String[] args) {
        int[] a = {3, 2, 3};
        majorityElement fs = new majorityElement();
        int res = fs.majorityElement1(a);

        System.out.println(res);}
    //hash法
    public int majorityElement1(int[] nums) {
        HashMap<Integer, Integer> has = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (!has.containsKey(nums[i])) {
                has.put(nums[i], 1);
            } else {
                has.put(nums[i], has.get(nums[i]) + 1);
            }
            if (has.get(nums[i]) > nums.length/2)
                return nums[i];
        }
        return 0;

    }
    //摩尔投票法
    public int majorityElement2(int[] nums) {
        int result = nums[0];
        int times = 1;
        for (int i = 1; i < nums.length; i++) {
            if (result == nums[i]) {
                times++;
            } else {
                times--;
                if (times == 0) {
                    result = nums[++i];
                    times++;
                }
            }
        }
        return result;
    }
}
